/* =============================================================
 * Your Grandmother's guide to Algorithms
 * =============================================================
 *
 * Copyright (c) 2007, Saverio Miroddi
 *
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without 
 * modification, are permitted provided that the following conditions are met:
 * 
 *     * Redistributions of source code must retain the above copyright notice,
 *       this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright 
 *       notice, this list of conditions and the following disclaimer in the 
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the SaverioMiroddiSoftware nor the names of its 
 *       contributors may be used to endorse or promote products derived from 
 *       this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *  
 * ---------------------------
 * Huffman.java
 * ---------------------------
 *
 */
package huffman;

import heaps.Heap;

/**
 * Huffman encoding.<br>
 * The interesting part is {@link #genStatsHeap(byte[]) genStatsHeap} and
 * {@link #createCodingTree(MinHeap) createCodingTree}, the rest is just
 * fooling around with bits & bytes.
 * <p>
 * From an OO perspective, there is a quite curious separation of
 * responsibilities.<br>
 * I'd like to see the coding routines out of the StatNode, but that's the
 * appropriate place.
 * 
 * @author Saverio Miroddi
 */
public class Huffman
{
	/**
	 * @param inputData
	 *            its length must be positive.
	 */
	public static EncodedData encode(byte[] inputData)
	{
		/* Generate an ordered queue of per-element statistics */
		Heap<StatNode> statsQueue = genStatsHeap(inputData);
		
		/* Generate the encoding/decoding tree */
		StatNode codingTree = createCodingTree(statsQueue);

		/* Encode and return */
		return codingTree.encode(inputData);
	}

	public static byte[] decode(EncodedData input) 
	{
		StatNode codingTree = input.codingTree;
		
		return codingTree.decode(input.data, input.totBits);
	}

	private static Heap<StatNode> genStatsHeap(byte[] data)
	{
		/* Get stats */
		
		StatNode[] stats = new StatNode[256];
		
		for (byte b: data) {
			int pos = b & 0xFF; // d*mn java
			
			if (stats[pos] == null) stats[pos] = new StatNode(b);
			else stats[pos].increase();
		}
		
		/* Clean, order and return */
		
		@SuppressWarnings("unchecked")
		Heap<StatNode> orderedStats = Heap.createMaxHeap();
		
		for (StatNode stat : stats)
			if (stat != null) orderedStats.insert(stat);

		return orderedStats;
	}

	private static StatNode createCodingTree(Heap<StatNode> statsQueue)
	{
		StatNode currNode = statsQueue.extractTop();
		
		// extract a node, merge with the current and reput in the queue.
		// wash, rinse and repeat until the last node standing
		while(true)
		{
			StatNode nextNode = statsQueue.extractTop();
			if (nextNode == null) break;
			
			StatNode merged = new StatNode(currNode, nextNode);
			statsQueue.insert(merged);
			
			currNode = statsQueue.extractTop();
		}
		
		// if we have only one char, we don't have still a tree, so we merge with
		// a phony node
		currNode = new StatNode(currNode, new StatNode((byte)0));
		
		return currNode;
	}
}